package h_Heap;

import java.util.Arrays;
import java.util.Random;

import a_ArrayList.ArrayList;

/**
 *@author 
 *heap为啥叫堆呢，就是因为他是个完全二叉树，像一个金字塔一样堆在那里；
 *DS里的堆和JVM里的堆完全是两个概念，但名字一模一样；
 *DS里的堆就是指，最大堆/最小堆；
 *
 *特性：
 *所有值是按层序一一加入堆里，即完全二叉树；
 *最大堆、最小堆：每个root的值都大于其所有subNode的值；整个堆的root是堆的最大值/最小值；
 *层层向下，每一层的均值递减/递增；
 *因为是存入数组，所以在这里按从0开始编号比较方便，则节点i的 LNode为2i+1，RNode为2i+2 (i>=0),父节点为：(i-1)/2(i>=1);
 *堆类似于广义的队列，只开放了堆顶和堆底两个口
 *
 *用来实现PriorityQueue，入队和出队都是O(logn),因为完全二叉树的优良结构，使其不会出现退化为链表的情况，最坏的情况仍然是O(logn)
 */
public class MinHeap_try<E extends Comparable<E>> {
	
	private ArrayList<E> data;

	public MinHeap_try(int capacity) {
		data = new ArrayList<>(capacity);
	}
	
	public MinHeap_try() {
		data = new ArrayList<>();
	}
	
	//由数组构建堆时：heapify 是 O(n)级别的。。具体证明需要用到高数等；而add操作是log(n)的 即遍历插入是O(nlogn)级别的 所以heapify更快一些；
	//遍历add对每一个元素都进行了siftup；但heapify的角度可以省去对叶子的操作，所以肯定会更快；二者角度不同，前者是从0到有，后者是先有再自适应；
	//这里第一次写时，i >= 0; for循环的结束条件用错了，写成了<=0, 这个参数是表示：在什么条件下一直循环；debug出来的
	public MinHeap_try(E[] e) {    //优化 用数组构建堆；避免了对叶子的操作从而减少了sift的次数；
		data = new ArrayList<>(e);
		for(int i = parent(data.getSize()-1); i >= 0; i--)
			siftDown(i);
 	}
	
	public boolean isEmpty() {
		return data.isEmpty();
	}
	
	//shift+ctrl+t打开类搜索
	public void add(E e) {
		data.addLast(e);
		siftUp(data.getSize()-1);                  //siftup和siftdown都是堆自适应的过程
	}
	private void siftUp(int index) {  	// O(logn) 将index对应的元素上浮到合适的位置
		while(index > 0 && data.get(index).compareTo(data.get(parent(index))) < 0) {
			data.swap(index,parent(index));
			index = parent(index);//这里也是debug出来的，迭代 如果每一轮过后不交换值.改变状态， 就是一个死循环了；
		}		
	}	
	private int parent(int index) {
		if(index > 0) {
			return (index-1)/2; 
		}
		throw new IllegalArgumentException("index "+index+" has no parent");
	}

	public E peek() {
		return data.get(0);
	}
	
	//在堆中关心的元素只有堆顶元素；
	public E remove() {
		E res = peek();
		data.swap(0,data.getSize()-1);
		data.removeLast(); //这一行 第一次写时漏掉了，debug出来的；
		siftDown(0);
		return res;
	}
	//这个递归写法，第一次就写对了        O(logn)        记住堆是类似队列的，只开放顶和底
	private void siftDown(int index) {     //*堆顶*变动破坏heap后的 下沉
		if(leftChild(index) >= data.getSize()) //没有左孩子  就没有孩子
			return;
		
		int min = leftChild(index); //这个写法很常用，也很关键，当需要比较大小的时候，可以先默认谁就是最值，然后看是否需要change；这样写，可以很好理解的判断另一方是否存在等等；
		if(rightChild(index) < data.getSize() && data.get(rightChild(index)).compareTo(data.get(min)) < 0)
			min = rightChild(index);
		
		if(data.get(min).compareTo(data.get(index)) < 0) {
			data.swap(min, index);
			siftDown(min);
		}	
		
		return; //这个可有可无，写上更好理解
		
	}
	private int rightChild(int index) {
		if(index < 0 && index >= data.getSize())
			throw new IllegalArgumentException("index is illegal");
		return 2*index+2 ;
	}
	private int leftChild(int index) {
		if(index < 0 && index >= data.getSize())
			throw new IllegalArgumentException("index is illegal");
		return 2*index+1;
	}
	
	//remove and replace the root
	public E replace(E e) {
		E res = peek();
		data.set(0, e);
		siftDown(0);
		return res;
	}

	@Override
	public String toString() {
		return data.toString();
	}


//    public static void main(String[] args) {
//
//        int n = 10;
//
//        MinHeap_try<Integer> minHeap = new MinHeap_try<Integer>();
////        Random random = new Random();
//        for(int i = n ; i > 0 ; i --)
//        	minHeap.add(i);
//
//        System.out.println("add into minHeap: "+minHeap);
//        
//        int[] arr = new int[n];
//        for(int i = 0 ; i < n ; i ++)
//            arr[i] = minHeap.remove();
//        
//        System.out.print("循环输出remove后最小堆的root: ");
//        for (int e : arr) {
//			System.out.print(e+" ");
//		}
//        System.out.println();
//
//        for(int i = 1 ; i < n ; i ++)
//            if(arr[i-1] > arr[i])
//                throw new IllegalArgumentException("Error");
//
//        System.out.println("Test minHeap completed.");
//    }
   
	
	/**
	 * test minHeap heapify
	 */
	public static void main(String[] args) {

        int n = 10;
        
        MinHeap_try<Integer> minHeap = new MinHeap_try<>(new Integer[]{10,9,8,7,6,5,4,3,2,1}) ;
//        Random random = new Random();
//        for(int i = n ; i > 0 ; i --)
//        	minHeap.add(i);

        System.out.println("add into minHeap: "+minHeap);
        
        int[] arr = new int[n];
        for(int i = 0 ; i < n ; i ++)
            arr[i] = minHeap.remove();
        
        System.out.print("循环输出remove后最小堆的root: ");
        for (int e : arr) {
			System.out.print(e+" ");
		}
        System.out.println();

        for(int i = 1 ; i < n ; i ++)
            if(arr[i-1] > arr[i])
                throw new IllegalArgumentException("Error");

        System.out.println("Test minHeap completed.");
    }
}
